package 作业;

import java.util.*;

public class Main{
    public static void main(String[] args) {
        char[] vertex ={'A','B','C','D','E','F','G'};
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N=65535;
        int e=0;
        for(int i=0;i<vertex.length;i++){
            for(int j=0;j<vertex.length;j++){
                String s= args[e++].toString();
                Integer it = Integer.parseInt(s);
                matrix[i][j]=it;
            }
        }
        /*100 5 7 100 100 100 2 
         25 100 100 9 100 100 3
         7 100 100 100 8 100 100
         100 9 100 100 100 4 100
         100 100 8 100 100 5 4
        100 100 100 4 5 100 6
         2 3 100 100 4 6 100
         */
        /*matrix[0]=new int[]{N,5,7,N,N,N,2};
        matrix[1]=new int[]{5,N,N,9,N,N,3};
        matrix[2]=new int[]{7,N,N,N,8,N,N};
        matrix[3]=new int[]{N,9,N,N,N,4,N};
        matrix[4]=new int[]{N,N,8,N,N,5,4};
        matrix[5]=new int[]{N,N,N,4,5,N,6};
        matrix[6]=new int[]{2,3,N,N,4,6,N}; */

        
        Graph graph = new Graph(vertex, matrix);
        //测试
        graph.showGraph();
        //测试一把
        graph.dsj(6);
        graph.showdijiesite();

    }
}
class Graph{
    private char[] vertex;
    private int [][] matrix;
    private VisitedVertex vv;
    //构造器
    public Graph(char[] vertex,int [][]matrix){
        this.matrix=matrix;
        this.vertex=vertex;
    }

    public void showdijiesite(){
        vv.show();
    }



    public void showGraph(){
        for(int[] link: matrix){
            System.out.println(Arrays.toString(link));
        }
    }



    //重头戏,suanfakaish
    public void dsj(int index){
        vv =new VisitedVertex(vertex.length, index);
        update(index);
        for(int j=1;j<vertex.length;j++){
            index = vv.updateArr();
            update(index);
        }
    }
    //耿昕index下表顶点到周围顶点的距离和恶前驱顶点；
    private void update(int index){
        int len=0;
        for(int j=0;j<matrix[index].length;j++)
        {
            len=vv.getDis(index)+matrix[index][j];
            if(vv.in(index)&&len<vv.getDis(j)){
                vv.updatepre(j, index);
                vv.updatedis(j, len);
            }
        }
    }




}
class VisitedVertex{
    public int[] already_arr;
    public int[] pre_visited;
    public int[] dis;
    //构造器
    public VisitedVertex (int length,int index){
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis=new int[length];
        //初始化
        Arrays.fill(dis, 65535);
        this.already_arr[index]=1;
        this.dis[index]=0;  
    }
    public boolean in(int index){
        return already_arr[index]==1;
    }



    public void updatedis(int index,int len){
        dis[index]=len;
    }


    public void updatepre(int pre,int index){
        pre_visited[pre]=index;
    }
//返回出发顶点到index顶点的剧
    public int getDis(int index){
        return dis[index]; 
    }
    public int updateArr(){
        int min = 65535,index=0;
        for(int i=0;i<already_arr.length;i++){
            if(already_arr[i]==0&&dis[i]<min){
                min = dis[i];
                index = i;
            }
        }
        already_arr[index]=1;
        return index;
    }
    //xianshi
    public void show(){
        System.out.println("====================");
        for(int i:already_arr){
            System.out.print(i+" ");
        }
        System.out.println(" ");
        for(int i:pre_visited){
            System.out.print(i+" ");
        }
        System.out.println(" ");
        for(int i:dis){
            System.out.print(i+" ");
        }
        System.out.println("");
        char[] vertex ={'A','B','C','D','E','F','G'};
        int count = 0;
        for(int i:dis){
            if(i!=65535){
                System.out.print(vertex[count]+"("+i+")");
            }else System.out.println("N");
        count++;
    }
    }
    
}